#include <bits/stdc++.h>

using namespace std;

class Solution
{
  private:
    vector<string> res;
    string tmp;
    int m_n;
    void backTrack(int left, int right)
    {
        if (left == m_n && right == m_n)
        {
            res.push_back(tmp);
            return;
        }
        if (left < m_n)
        {
            tmp.push_back('(');
            backTrack(left + 1, right);
            tmp.pop_back();
        }
        if (right < left)//判断合法的关键
        {
            tmp.push_back(')');
            backTrack(left, right + 1);
            tmp.pop_back();
        }
    }

  public:
    vector<string> generateParenthesis(int n)
    {
        m_n = n;
        res.clear();
        backTrack(0, 0);
        return res;
    }
};